package 二叉树;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class _145_二叉树的后序遍历 {
	public List<Integer> postorderTraversal(TreeNode root) {
		List<Integer> list = new LinkedList<Integer>();
		if (root == null) return list;
		Stack<TreeNode> stack = new Stack<>();
		TreeNode cur = root;
		TreeNode last = null;
		while (!stack.isEmpty() || cur != null) {
			if (cur != null) {
				stack.push(cur);
				last = cur;
				cur = cur.left;
			} else {
				cur = stack.peek();
				if (cur.right != null && cur.right != last) {
					last = cur;
					cur = cur.right;
				} else {
					cur = stack.pop();
					list.add(cur.val);
					last = cur;
					cur = null;
				}
			}
		}
		return list;
	}
}
